package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

import java.util.Stack;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 21:45
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。
保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。
 */
public class h_求BST某节点后继 {
    public static void main(String[] args) {
        h_求BST某节点后继 test = new h_求BST某节点后继();
        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree = new b_MyBinaryTreebyLinked<>();

        binaryTree.insert(6,6);
        BSTNode<Integer, Integer> node1 = binaryTree.insert(7, 7);
        binaryTree.insert(4,4);
        binaryTree.insert(5,5);
        BSTNode<Integer, Integer> node = binaryTree.insert(8, 8);
        binaryTree.insert(2,2);

        System.out.println(test.successor1(node1,7));
        test.successor2(node1,7);
        System.out.println(test.result);
        System.out.println(binaryTree);
    }

    /**
     * 利用中序遍历迭代形式
     * @param node
     * @param p
     * @return
     */
    public Integer successor1(BSTNode<Integer,Integer> node, Integer p) {
        if (node == null) {
            return -1;
        }

        Stack<BSTNode<Integer, Integer>> stack = new Stack<BSTNode<Integer,Integer>>();
        BSTNode<Integer,Integer> current = node;
        boolean isFound = false;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.add(current);
                current = current.left;
            }
            if (!stack.isEmpty()) {
                BSTNode<Integer,Integer> popElement = stack.pop();
                if (isFound) {
                    return popElement.value;
                } else if (popElement.value.equals(p)) {// 如果弹出节点的value值和p相同，那么下次弹出的值就是我们需要的值，修改标志位
                    isFound = true;
                }
                current = popElement.right;
            }
        }
        return -1;
    }

    private Integer preValue = Integer.MIN_VALUE;
    private Integer result = -1;

    /**
     * 利用中序遍历递归形式
     * @param node
     * @param p
     */
    public void successor2(BSTNode<Integer,Integer> node, Integer p) {
        if (node == null) {
            return;
        }
        successor2(node.left, p);
        if (preValue.equals(p)) {
            if (result != -1) {
                return;
            }
            result = node.value;
            return;
        }
        preValue = node.value;
        successor2(node.right, p);
    }
}
